//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 
// 
// 
// 
// Related Topics 数组 回溯 
// 👍 1107 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class NQueens {
    public static void main(String[] args) {
        new NQueens().new Solution().solveNQueens(9);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * N皇后问题，莽就完了，回溯的经典题目
     * 传递的层数作为的遍历，如果到了最外层就添加结果
     *
     * 优化：使用Boolean数组记录已经拜访的皇后位置
     * 只需要储存列占用情况和对角线占用情况
     * 主对角线上的元素行-列坐标值都是一样的，次对角线上行+列坐标值都是一样的
     */
    class Solution {
        int len;
        List<List<String>> res = new ArrayList<>();
        //Set<Integer> colUsed;
        //Set<Integer> main;
        //Set<Integer> sub;
        public List<List<String>> solveNQueens(int n) {
            len = n;
            //colUsed = new HashSet<>();
            //main = new HashSet<>();
            //sub = new HashSet<>();
            List<List<String>> res = new ArrayList<>();
            char[][] board = new char[n][n];
            for (char[] chars : board) Arrays.fill(chars, '.');
            dfs(0,board,n,res);
            return res;
        }

        private void dfs(int index,char[][] board,int n ,List<List<String>> res) {
            if (index == n){
                List<String> temp = new ArrayList<>();
                for (char[] chars : board) temp.add(new String(chars));
                res.add(new ArrayList<>(temp));
            }else {
                for (int i = 0; i < n ; i++) {
                    /*// 这里是使用HashSet来存储各列，主对角线次对角线的占用情况
                    //主对角线上行-列全是相同的值，次对角线行+列都是相同的值
                    if (board[index][i] == '.' && !colUsed.contains(i)&&!main.contains(index-i)
                            && !sub.contains(index+i)){
                        colUsed.add(i);
                        main.add(index-i);
                        sub.add(index+i);
                        board[index][i] = 'Q';
                        dfs(index+1, board, n, res);
                        board[index][i] = '.';
                        colUsed.remove(i);
                        main.remove(index-i);
                        sub.remove(index+i);

                    }*/
                    if (board[index][i]=='.' && isValid(index,i,board)){
                        board[index][i] = 'Q';
                        dfs(index+1, board, n, res);
                        board[index][i] = '.';
                    }
                }
            }
        }
        private boolean isValid(int x, int y, char[][] board) {
            for (int i = 0; i < x ; i++) {//判断当前列是否被占用
                if (board[i][y] == 'Q') return false;
            }
            for (int i = x-1,j = y-1; i >=0&&j>=0 ; i--,j--) {//判断主对角线
                if (board[i][j]=='Q') return false;
            }
            for (int i = x-1,j = y+1; i >=0&&j<len ; i--,j++) {//判断次对角线
                if (board[i][j]=='Q') return false;
            }
            return true;
        }


        //二刷没什么差别，还是想不出使用对角线值的方法来判断是否占用
        public void dfs(char[][] board, int n, int row){
            if (row == n){
                List<String> temp = new ArrayList<>();
                for(char[] s : board) temp.add(new String(s));
                res.add(new ArrayList(temp));
            }else{
                for (int i = 0; i < n; i++){
                    if(isValid2(row,i,board)){
                        board[row][i] = 'Q';
                        dfs(board,n,row+1);
                        board[row][i] = '.';
                    }
                }
            }
        }
        public boolean isValid2(int row, int col, char[][] board){
            for(int i = 0; i < row; i++) if(board[i][col] == 'Q') return false;
            for(int i = row-1, j = col-1; i>=0&&j>=0; i--, j--) if(board[i][j] == 'Q') return false;
            for(int i = row-1, j = col+1; i>=0&&j<board[0].length; i--, j++) if(board[i][j] == 'Q') return false;
            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}